<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8" />
    <title>TopCoder SRM 659 - 1000: ApplesAndOrangesHard</title>
    
    <link type="image/x-icon" rel="shortcut icon" href="http://www.topcoder.com/i/favicon.ico"/>
    

    
    <style type="text/css">
        /* font */
body {
    font-family: Helvetica, Arial, Verdana, sans-serif;
    font-size: 16px;
    line-height: 1.2em;
}
ul.constraints > li:before, ul.notes > li:before {
    font-family: monospace;
    font-weight: normal;
}
.heading {
    font-weight: bold;
    font-size: 175%;
    line-height: 1.2em;
}
.section .section-title {
    font-weight: bold;
    font-size: 125%;
}
ol.testcases > li:before {
    font-family: monospace;
}
type {
    font-weight: bold;
    font-family: monospace;
}
li.testcase .data {
    font-family: monospace;
    line-height: 1.5em;
}

/* layout */
.heading {
    margin-top: 0.1em;
    margin-bottom:0.1em;
    text-align: center;
}
.section .section-title {
    margin-top : 1em;
    margin-bottom: 1em;
}
.problem-intro, note, user-constraint {
    padding-left: 1.25em;
}

/* Lists */
ul.constraints, ul.notes, ul.variables, ul.problem-definition-lines {
    list-style-type: none;
    padding: 0px;
}
ul.constraints > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}
ul.notes > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}

/* Testcases */
li.testcase {
    line-height: 1.1em;
    padding-top: 0.625em;
    padding-bottom: 0.625em;
    overflow: auto;
}
li.testcase > .testcase-content > div { padding-bottom: 0.5em; padding-left: 1em; }

li.testcase .testcase-comment {
    margin: 0;
    padding-left: 1em;
}
.testcase-comment p:first-child { margin-top: 0; }
.testcase-comment p:last-child { margin-bottom: 0; }

li.testcase .testcase-content {
    margin: 0.31em;
}

/* Data and variables */
.testcase-output {
    padding: 0.2em 1em 0.2em 0em;
}
.variables, .testcase-output {
    margin-left: 0.5em;
    display: table;
    margin-bottom: 0px;
    margin-top: 0px;
}
.variable {
    display: table-row;
}
.variable .name {
    padding: 0.2em 0em 0.2em 1em;
    font-weight: bold;
    display: table-cell;
    text-align: right;
}
.testcase-output .prefix {
    padding: 0.2em 0em 0.2em 1em;
    display: table-cell;
}
.testcase-output .prefix:after {
    content : ":";
    padding-right: 0.5em;
}
.variable .name:after {
    font-weight: bold;
    content : ":";
    padding-right: 0.5em;
}
.variable .value, .testcase-output .value {
    padding: 0.2em 1em 0.2em 0em;
    display: table-cell;
}
ol.testcases {
    padding: 0px;
    counter-reset: test_number -1;
}
ol.testcases > li {
    list-style:none;
}
ol.testcases > li:before {
    counter-increment:test_number;
    display: block;
    clear: both;
    content:counter(test_number) ")";
    color: inherit;
    background: inherit;
}

/* Problem Definition */
.problem-definition, .problem-limits {
    padding-left: 1.25em;
}
.problem-definition-lines, .limit-lines {
    display: table;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-left: 0px;
}
.definition-line, .limit-line {
    display: table-row;
    height: 1.5em;
    overflow: auto;
}
.limit-name:after {
    content: ":";
    margin-right: 1em;
}
.definition-name, .definition-value, .limit-name, .limit-value {
    display: table-cell;
}
.definition-value {
    padding-left: 0.5em;
}
.definition-name:after {
    content: ":";
}
#contest-division:before {
    content: "Div ";
}
#problem-score:before {
    content: "- Problem ";
}
#problem-name {
    display: block;
}

/* Tags, hidden default */
.tag {
    visibility: hidden;
    position: absolute;
}

        body {
    /* font color */
    color: #333333;
    /* background color */
    background-color: white;
}
.section .section-title {
    /* title color */
    color: black;
}
li.testcase .data {
    /* highlight color */
    background: #eee;
}

    </style>
    
    
    

</head>

<body>
    <h1 class="heading">
        <span id='contest-name'>SRM 659</span>
        <span id='contest-division'>2</span>
        <span id='problem-score'>1000</span>
        <span id='problem-name'>ApplesAndOrangesHard</span>
    </h1>

    <hr />

    <!-- Problem Statement -->
    <div class="section">
        <h2 class="section-title">Problem Statement</h2>
        <div class="problem-intro">
            <intro escaped="1">Garth likes apples and oranges. Recently he bought <b>N</b> fruits, where each fruit was either an apple or an orange. Then he ate all <b>N</b> fruits in some order. You are given an <type>int</type> <b>K</b>. Garth observed that at every point in time, if he made a list of the last <b>K</b> fruits he ate, there were at most <b>K</b>/2 (rounded down) apples in this list.
<br />
<br />
For each valid i, you know that the <b>info</b>[i]-th fruit Garth ate was an apple. (Fruits Garth ate are numbered starting from 1. For example, <b>info</b>[i]=1 means that the very first fruit Garth ate was an apple.)
<br />
<br />
Please find and return the maximum number of apples Garth could have eaten.</intro>
        </div>
    </div>
    
    <!-- Problem definition -->
    
    <div class="section" id="definition">
        <h2 class="section-title">Definition</h2>
        <div class="problem-definition">
            <ul class="problem-definition-lines">
                <li class="definition-line" id='class-line'>
                    <span class='definition-name'>Class</span>
                    <span class='definition-value'>ApplesAndOrangesHard</span>
                </li>
                <li class="definition-line" id='method-line'>
                    <span class='definition-name'>Method</span>
                    <span class='definition-value'>maximumApples</span>
                </li>
                <li class="definition-line" id='parameters-line'>
                    <span class='definition-name'>Parameters</span>
                    <span class='definition-value'>
                    
                        integer
                    , 
                        integer
                    , 
                        tuple(integer)
                    
                    </span>
                </li>
                <li class="definition-line" id='returns-line'>
                    <span class='definition-name'>Returns</span>
                    <span class='definition-value'>
                        integer
                    </span>
                </li>
                <li class="definition-line" id='signature-line'>
                    <span class='definition-name'>Method signature</span>
                    <span class='definition-value'>
                        def maximumApples(self, N, K, info)
                    </span>
                </li>
            </ul>
            <div class="problem-definition-public-tip">(be sure your method is public)</div>
        </div>        
    </div>
    

    <!-- Limits -->
    <div class="section">
        <h2 class="section-title">Limits</h2>
        <div class='problem-limits'>
            <ul class="limit-lines">
                <li class='limit-line'>
                    <span class='limit-name'>Time limit (s)</span>
                    <span class='limit-value'>2.000</span>
                </li>
                <li class='limit-line'>
                    <span class='limit-name'>Memory limit (MB)</span>
                    <span class='limit-value'>256</span>
                </li>
            </ul>
        </div>
    </div>

    
    <!-- Notes -->
    <div class="section">
        <h2 class="section-title">Notes</h2>
        <ul class="notes">
        
            <li><note escaped="1">If Garth makes his list at a point in time when he ate fewer than <b>K</b> fruits, his list will have fewer than <b>K</b> fruits but the requirement will still be the same: there have to be at most <b>K</b>/2 apples in the list.</note></li>
        
        </ul>
    </div>
    
    
    <!-- Constraints -->
    <div class="section">
        <h2 class="section-title">Constraints</h2>
        <ul class="constraints">
        
            <li><user-constraint escaped="1"><b>N</b> will be between 2 and 1,000,000,000, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>K</b> will be between 2 and min(100,000, <b>N</b>), inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>info</b> will contain between 0 and 50 elements, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1">Each element of <b>info</b> will be between 1 and <b>N</b>, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1">The elements of <b>info</b> will be distinct.</user-constraint></li>
        
            <li><user-constraint escaped="1">The elements of <b>info</b> will be consistent with Garth's observation.</user-constraint></li>
        
        </ul>
    </div>

    <!-- Test cases -->
    <div class="section">
        <h2 class="section-title">Test cases</h2>
        <ol class="testcases" start='0'>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    3
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    2
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    {  }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            2
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">Garth ate <b>N</b>=3 fruites. The requirement is that any <b>K</b>=2 consecutive fruits may contain at most <b>K</b>/2 = 1 apple. As <b>info</b> is empty, you have no additional information about the fruits Garth ate.
<br />
<br />
Garth might have eaten an apple, then an orange, then an apple. This satisfies the conditions:
<ul>
<li>After eating the 1st fruit, the list is [apple].</li>
<li>After eating the 2nd fruit, the list is [apple, orange].</li>
<li>After eating the 3rd fruit, the list is [orange, apple].</li>
</ul>
Each list contains at most 1 apple.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    10
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    3
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    { 3, 8 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            2
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">All fruits, except for the 3rd and the 8th, must have been oranges.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    9
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    { 1, 4 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            5
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    9
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    { 2, 4 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            4
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    23
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    7
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    { 3, 2, 9, 1, 15, 23, 20, 19 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            10
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">N</span>
                                <span class="value data">
                                
                                    1000000000
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">K</span>
                                <span class="value data">
                                
                                    17
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">info</span>
                                <span class="value data">
                                
                                    { 2110119, 401933834, 401933833, 10 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            470588238
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
        </ol>
    </div>
    <hr />

    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
</body>
</html>
